package everyday;

import javax.swing.tree.TreeNode;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/6/10 11:01
 * 114. 二叉树展开为链表
 */
public class Solution114 {

    // 前驱节点发
    public void flatten2(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode cur = root;
        while (cur != null) {
            // 先找到二叉树左子树的最右节点作为前驱节点
            if (cur.left != null) {
                TreeNode pre = cur.left;
                while (pre != null && pre.right != null) {
                    pre = pre.right;
                }
                // 右子树挂在左子树的最右节点
                pre.right = cur.right;
                cur.right = cur.left;
                // 断开左子树
                cur.left = null;
            }
            // 继续遍历迭代
            cur = cur.right;
        }
    }

        // 前序遍历法
    public void flatten(TreeNode root) {
        if (root == null) {
            return;
        }
        // 非递归的方式将二叉树的前序遍历节点序列添加到 list 中存储
        List<TreeNode> list = new ArrayList<>();
        Deque<TreeNode> stack = new ArrayDeque<>();  // 用于前序遍历的辅助栈
        TreeNode curNode = root;
        while (curNode != null || !stack.isEmpty()) {
            while (curNode != null) {
                list.add(curNode);
                stack.push(curNode);
                curNode = curNode.left;
            }
            curNode = stack.poll();
            curNode = curNode.right;
        }
        // 转化成为单链表
        TreeNode pre = null;
        for (int i = 1; i < list.size(); i++) {
            pre = list.get(i - 1);
            curNode = list.get(i);
            pre.left = null;
            pre.right = curNode;
            pre = pre.right;
        }
    }

      private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
